package com.ryujung.sort;

import java.util.Arrays;

public class MergeSort {

    /**
     * 归并排序是建立在归并操作上的一种有效的排序算法。
     * 
     * 该算法是采用分治法（Divide and Conquer）的一个非常典型
     * 的应用。将已有序的子序列合并，得到完全有序的序列；
     * 即先使每个子序列有序，再使子序列段间有序。
     * 若将两个有序表合并成一个有序表，称为2-路归并。
     * 
     * 思路：
     * 1. 分治，将整个数组拆分
     * 2. 将拆分后的数组进行排序
     * 3. 将所有排序好的数组合并
     * 
     * 步骤：
     * 1. 通过指定角标的方式将数组拆分
     */
    public static int[] mergeSort(int[] arr) {
        return partitionAndMerge(arr, 0, arr.length - 1);
    }

    private static int[] partitionAndMerge(int[] arr, int l, int r) {
        if (r - l < 1) {
            return new int[] { arr[l] };
        }
        int mid = (r + l) / 2;
        int[] left = partitionAndMerge(arr, l, mid);
        int[] right = partitionAndMerge(arr, mid + 1, r);
        int[] result = merge(left, right);
        return result;
    }

    private static int[] merge(int[] left, int[] right) {
        int l1 = 0, l2 = 0;
        int[] result = new int[left.length + right.length];
        int index = 0;
        while (l1 < left.length && l2 < right.length) {
            result[index++] = left[l1] < right[l2] ? left[l1++] : right[l2++];
        }

        while (l1 < left.length) {
            result[index++] = left[l1++];
        }

        while (l2 < right.length) {
            result[index++] = right[l2++];
        }
        return result;
    }

    public static void mergeSort2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        mergeHelper(arr, 0, arr.length - 1);
    }

    private static void mergeHelper(int[] arr, int i, int j) {
        int mid = (i + j) / 2;
        if (i < j) {
            mergeHelper(arr, i, mid);
            mergeHelper(arr, mid + 1, j);
        }
        int l = i, r = mid + 1, index = 0;
        int[] tmp = new int[j - i + 1];
        while (l <= mid && r <= j) {
            tmp[index++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
        }
        while (l <= mid) {
            tmp[index++] = arr[l++];
        }
        while (r <= j) {
            tmp[index++] = arr[r++];
        }
        index = 0;
        for (int k = i; k <= j; k++) {
            arr[k] = tmp[index++];
        }
    }

    public static void main(String[] args) {
        int[] arr = { 2, 1 };
        int[] arr1 = { 5, 3, 8, 6, 4 };
        int[] arr2 = { 3, 1, 4, 2, 5 };
        int[] arr3 = { 9, 7, 6, 2, 4, 3, 1, 5, 8 };

        // arr = mergeSort(arr);
        // System.out.println(Arrays.toString(arr));
        // arr1 = mergeSort(arr1);
        // System.out.println(Arrays.toString(arr1));
        // arr2 = mergeSort(arr2);
        // System.out.println(Arrays.toString(arr2));
        // arr3 = mergeSort(arr3);
        // System.out.println(Arrays.toString(arr3));

        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
        mergeSort2(arr1);
        System.out.println(Arrays.toString(arr1));
        mergeSort2(arr2);
        System.out.println(Arrays.toString(arr2));
        mergeSort2(arr3);
        System.out.println(Arrays.toString(arr3));
    }

}
